package LeetCode.exercise;

import java.util.LinkedList;
import java.util.Queue;

public class LC1020 {
    public int numEnclaves(int[][] grid) {
        Queue<int[]> q = new LinkedList<>();
        int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
        int res = 0, m = grid.length, n = grid[0].length;
        boolean[][] flag = new boolean[m][n];
        for(int i = 0; i < n; i++){
            if(grid[0][i] == 1){
                flag[0][i] = true;
                q.offer(new int[]{0, i});
            }
            if(grid[m-1][i] == 1){
                flag[m-1][i] = true;
                q.offer(new int[]{m-1, i});
            }
        }
        for(int i = 0; i < m; i++){
            if(grid[i][0] == 1 && !flag[i][0]){
                flag[i][0] = true;
                q.offer(new int[]{i, 0});
            }
            if(grid[i][n-1] == 1 && !flag[i][n-1]){
                flag[i][n-1] = true;
                q.offer(new int[]{i, n-1});
            }
        }
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int a = tmp[0], b = tmp[1];
            for(int i = 0; i < 4; i++){
                int x = a + dx[i], y = b + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n
                        && grid[x][y] == 1 && !flag[x][y]){
                    flag[x][y] = true;
                    q.offer(new int[]{x, y});
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!flag[i][j] && grid[i][j] == 1){
                    res++;
                }
            }
        }
        return res;
    }
}
